#include <stdio.h>

typedef struct _node_t {
    int value;
    struct _node_t *left;
    struct _node_t *right;
} node_t;

void bst2list(node_t *root, node_t **head, node_t **tail)
{
    if (!root) {
        return;
    }
    node_t *t;
    if (!root->left) {
        *head = root;
    } else {
        bst2list(root->left, head, &t);
        t->right = root;
        root->left = t;
    }
    if (!root->right) {
        *tail = root;
    } else {
        bst2list(root->right, &t, tail);
        root->right = t;
        t->left = root;
    }
}

int main()
{
    node_t t1, t2, t3, t4, t5, t6, t7, t8;
    node_t *head, *tail;
    t1.value = 1;
    t2.value = 2;
    t3.value = 3;
    t4.value = 4;
    t5.value = 5;
    t6.value = 6;
    t7.value = 7;
    t8.value = 8;
    t4.left = &t2;
    t4.right = &t6;
    t2.left = &t1;
    t2.right = &t3;
    t6.left = &t5;
    t6.right = &t7;
    t7.right = &t8;
    t1.left = t1.right = 0;
    t3.left = t3.right = 0;
    t5.left = t5.right = 0;
    t7.left = 0;
    t8.left = t8.right = 0;
    bst2list(&t4, &head, &tail);
    while (head) {
        printf("%d\n", head->value);
        head = head->right;
    }
    return 0;
}

